/**
 * 你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
 *
 * 返回符合要求的 最少分割次数 。
 *
 *
 */
class MinCut {
    /**
     * 方法：动态规划
     *
     * 状态：
     *  子状态：到第1,2,3,...,n个字符需要的最小分割数
     *  F(i): 到第i个字符需要的最小分割数
     *
     * 状态递推：
     *  F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串
     *  上式表示如果从j+1到i判断为回文字符串，且已经知道从第1个字符
     *  到第j个字符的最小切割数，那么只需要再切一次，就可以保证
     *  1-->j, j+1-->i都为回文串。
     *
     * 初始化：
     *  F(i) = i - 1
     *  上式表示到第i个字符需要的最大分割数
     *  比如单个字符只需要切0次，因为单子符都为回文串
     *  2个字符最大需要1次，3个2次......
     *
     * 返回结果：
     *  F(n)
     *
     * 遗留问题：如何判断一段字符串为回文串
     *  循环判断首尾元素是否相同，如果全部相同，则是回文串
     * @param s
     * @return
     */
    public int minCut(String s) {
        int len=s.length();
        int[] dp=new int[len+1];
        if(len==0) {
            return 0;
        }
        for(int i=0;i<=len;i++) {
            dp[i]=i-1;
        }
        for(int i=1;i<=len;i++) {
            for(int j=0;j<i;j++) {
                if(isPail(s,j,i-1)) {
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[len];
    }
    public boolean isPail(String s,int left,int right) {
        while(left<right) {
            if(s.charAt(left)!=s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    /**
     * 判断回文串的方法可以继续优化，使总体时间复杂度将为O(n^2)
     *
     * 判断回文串，这是一个“是不是”的问题，所以也可以用动态规划来实现
     *
     * 判断回文串：动态规划
     *
     * 状态：
     *  子状态：从第一个字符到第二个字符是不是回文串，第1-3，第2-5，...
     *  F(i,j): 字符区间 [i,j] 是否为回文串
     *
     * 状态递推：
     *  F(i,j): true->{s[i]==s[j] && F(i+1,j-1)} OR false
     *  上式表示如果字符区间首尾字符相同且在去掉区间首尾字符后字符区间仍为回文串，
     *  则原字符区间为回文串
     *  从递推公式中可以看到第i处需要用到第i+1处的信息，所以i应该从字符串末尾遍历
     *
     * 初始化：
     *  F(i,j) = false
     *
     * 返回结果：
     *  矩阵F(n,n), 只更新一半值（i <= j），n^2 / 2
     */
//    public boolean[][] getMat(String s){
//        int len = s.length();
//        boolean[][] Mat = new boolean[len][len];
//        for(int i = len - 1; i >= 0; --i){
//            for(int j = i; j < len; ++j){
//                if(j == i)
//                    // 单字符为回文字符串
//                    Mat[i][j] = true;
//                else if(j == i + 1){
//                    // 相邻字符如果相同，则为回文字符串
//                    if(s.charAt(i) == s.charAt(j))
//                        Mat[i][j] = true;
//                    else
//                        Mat[i][j] = false;
//                }
//                else{
//                    // F(i,j) = {s[i]==s[j] && F(i+1,j-1)
//                    // j > i+1
//                    Mat[i][j] = (s.charAt(i) == s.charAt(j)) && Mat[i + 1][j - 1];
//                }
//            }
//        }
//        return Mat;
//    }
//    public int minCut(String s) {
//        int len = s.length();
//        if(len == 0)
//            return 0;
//        boolean[][] Mat = getMat(s);
//        int[] minCut = new int[len + 1];
// // F(i)初始化
//        // F(0）= -1，必要项，如果没有这一项，对于重叠字符串“aaaaa”会产生错误的结果
//        for(int i = 0; i <= len; ++i){
//            minCut[i] = i - 1;
//        }
//
//       
//        for(int i = 1; i <= len; ++i){
//            for(int j = 0; j < i; ++j){
//                // F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串
//                // 从最长串判断，如果从第j+1到i为回文字符串
//                // 则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
//                if(Mat[j][i - 1]){
//                    minCut[i] = Math.min(minCut[i], minCut[j] + 1);
//                }
//            }
//        }
//        return minCut[len];
//    }
}

/*

上述方法判断回文串时间复杂度O(n^2)

主方法两次循环时间复杂度O(n^2)

总体时间复杂度O(n^2) ~ O(2 * n^2) = O(n^2) + O(n^2)


总结：
 简单的动态规划问题，状态，状态递推和状态初始化都比较直观
 对于复杂的动态规划问题，状态，状态递推和状态初始化都比较隐含，需要仔细推敲
 尤其是状态递推可能需要额外的辅助判断条件才能达成。

*/

}